三 Bounding Function: Inductive Cases

估計 B(N,k)

延續上次所講的表格，要來填 N 大於 k 的部分。

以 B(4,3) 為例，其符合規定的 dichotomies 算出來是 11 種。( 4 個點中 任意 3 個皆無法 shattered )

此時要來試著找出它與 B(3,?) 間的關聯性。

從圖中可以看出 11 種 可以再區分成 兩類。排除 $x_4$ 來看可以發現:

• 有一類是 成對 的，也就是它前 3 個點一樣，第 4 的點有 o,x 兩種。
• 另一類則是 不成對 的。

寫成簡單的式子: $B(4,3) = 2\alpha + \beta$

排除掉 $x_4$ 後的 dichotomies $(x_1,x_2,x_3)$: $\alpha + \beta$
而這三個點不能有 shattered 的情形發生，否則就違反 k = 3 的限制了。
這麼一來，就可以知道 $\alpha + \beta \le B(3,3)$ 。

接著來看 $\alpha$ ，圖中橘色的部分，我們已經知道 $\alpha$ 的 dichotomies 如果加回 $x_4$ 是 成對的 (o,x)。再進一步也就是說 $(x_1,x_2,x_3)$ 中 任兩點 皆不能 shattered ，否則加回 $x_4$ 後，就會發生 三個點 shattered 的情形，違反 k = 3 的限制了。
所以可以得知: $\alpha \le B(3,2)$

整理一下:

我們還不能確定它等於哪個值，但我們現在可以知道 B(N,k) 的上限了。

B(N,k) 的上限

推導可以透過表格的邊界和遞迴式，用數學歸納法。

從一開始的 growth function 到其 上限函數 B(N,k) ，現在則是 B(N,k) 的上限了，而 B(N,k) 的上限則會是某個 poly(N) ，最高項 $N^{k-1}$。
最後則能得到結論:

growth function 如果有 break point ，最後就會是個多項式。

p.s. 這邊的小於等於可以換成等於

一些例子:

其中 2D perceptrons 的 growth function 雖然不知道，但現在能知道其上限了。
也就是說不管 growth function 怎麼樣，只要能找到 break point ，其成長的速度最多就會跟 多項式 一樣快。

練習

N > 2 的時候成長函數就會小於它了，它是上限。

四 A Pictorial Proof

這邊很多地方沒有搞得很清楚，看看就好…

BAD Bound

回過頭來看 Hoeffding 的式子，我們已經知道 growth function 最後的上限會是 poly ，那是不是可以直接放進公式呢？

不行

現在則要證明實際上是怎樣？我們只能給出實際上差不多的版本，而其首要條件是 N 要夠大。
(這邊接下來幾乎都是證明了，老實說幾乎不太懂…)

接下來要解釋那些多出來的常數是怎麼發生的。

Step 1

我們有興趣的是壞事情發生的機率，這邊順便複習一下之前的觀念。

BAD event: $E_{in}$ 和 $E_{out}$ 相差很多。
BAD data: 對某些 h ，它會發生 BAD event。

而我們希望 BAD data 出現的機率不要太高 (也就是圖中的算式)。

先看看 $E_{in}(h)$ ，跟 data 有關，最多 N 個點，所以其成長函數就是在 N 的地方。
那 $E_{out}(h)$ 卻有 無限 個點，舉例來說，平面上有無限多條線，只要轉一下，$E_{out}(h)$ 就會改變(或許很小)。所以我們無法直接來使用它。

而現在的目標就是要把 $E_{out}$ 換成 有限 個。 首先就是要變成 有限 個點，用 先前 所講 verification 的觀念，利用有限多個點來推 $E_{out}$。
而這有限多個點，可以想成另外 N 個點，叫做 $D^\prime$。其估算出來的 $E_{out}$ 稱為 $E_{in}^\prime$。
我們又把 $D^\prime$ 稱作 ghost data。

圖中右邊可以看到一張圖，我們把所有 Data set 產生出來的 $E_{in}$ 列出來，它中心應該會是在 $E_{out}$。
這邊簡單來說就是當 $E_{in}$ 和 $E_{out}$ 相差很遠時，有很大的機會(線形圖中的 綠色 部分)再抽一組 $E_{in}^\prime$ ，$E_{in}^\prime$ 和 $E_{in}$ 也相差得很遠。

這樣就可以將 $E_{out}$ 給替換掉了，需要改動一下式子。
(解釋我就不打了，沒有很理解，附上 影片 )

Step 2

我們已經將本來無限多個點的 $E_{out}(h)$ 給替換掉了，接著對於有限的 $D$ 和 $D^\prime$ 就可以拿出 $m_H$ 來用了。

本來 無限 多種的 hypothesis 可以分成 $m_H(N)$ 種，現在多了 $D^\prime$ ，總共 2N 個點，而此時 hypothesis 可能會有 重疊 的部分，所以我們要把 BAD event 發生時情形是一樣的來 分類(如同 之前 的說明)，可以得知 hypothesis 種類數的 Union Bound ，也就是 dichotomies 最多的種類數就變成了 $m_H(2N)$ 。

也就是算式中多的 $m_H(2N)$ 種和 固定要驗證的那個 h。

Step 3

現在要來計算 $E_{in}$ 和 $E_{in}^\prime$ 的差別，要知道兩次 sample 的差別，就好像先取 2N 個，抓其中 N 個比較剩下的 N 個或是比較全部 2N 的平均。(利用 Hoeffding，blablabla…)

VC bound

經過剛剛，我們用超級簡略的方式(揮揮手XD)證明了一個非常重要的定理。

可以看一下式子中顏色對應的解釋。

對於 2D perceptrons ，它 break point 是 4，也就是它 growth function 最多不會跑得比 $O(N^3)$ 快(上節的內容)。

結論來說我們說明了在 2D perceptrons 中，只要 N 夠大，我們挑 $E_{in}$ 最小的，而挑出來的 hypothesis g 在 $E_{out}$ 也大概會是最小的，也就達到了機器學習所要的效果。

練習與總結

帶數字去算即可。

從 break point 產生出的 B(N,k) 到用它來推算成長函數，還有它們的上限。最後則是用成長函數來替換掉 M 的證明。